package num55II;

/**
 * @author : DuJiabao
 * @Date : 2021/1/22 18:48
 * @Project : sword-finger-offer
 * @File : null.java
 * @Desc :输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
 */

/**
 * 这题用分治思想。比较难想到的是，发现下面已经不是平衡二叉树了之后，该怎么向上传递。
 * 此方法，通过传递 -1 的方法，只要遇到下面的枝叶返回-1，就立即返回-1.
 * 否则，就计算左右子树的深度之差，如果超过2，就返回-1.否则返回其中深度较大的+1（因为深度由深的决定）
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = recur(root.left);
        if (left == -1) return -1;
        int right = recur(root.right);
        if (right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}
